\section{整除与带余除法}

\begin{frame}{整除}
开辟鸿蒙， 先有数一。 一加一为二， 二加一为三。 如此继续， 生出自然数。
\pause
自然数 $1,2,3, \cdots$ 的集合记为 $\mathbb{N}$. 这是人类智慧知识的发源家园。 
\pause
自然数集合 $\mathbb{N}$内部， 数之间可加可乘， 但相减则不一定可行。
($\NN$带上乘法或加法是半群。)

\pause
随着人类智慧渐开， 人们逐渐承认 $0$ 是 “数”, 又承认 $0-1=2-3=3-4$, $0-2=1-3=2-4$ 等为 “数”, 记为 $-1,-2$ 等; 它们与自然数一起合称为\emph{整数} (integers). 
\pause
整数的集合记为 $\mathbb{Z}$ (源自德文 Zahlen), 即
\[
\mathbb{Z}=\{\cdots,-3,-2,-1,0,1,2,3, \cdots\}
\]
\pause
整数集合 $\mathbb{Z}$ 内部， 整数之间可以相加、相减、相乘， 且其结果 (分别称为\emph{和、差、积}) 仍然是整数。 此性质被称为\emph{整数集合 $\mathbb{Z}$ 对加、减、乘运算是封闭的}。
\pause
注意， \emph{整数集合 $\mathbb{Z}$ 对除法不封闭} (例如除法 $3 \div 2$ 在 $\mathbb{Z}$ 中不能进行， 或者说在 $\mathbb{Z}$中无结果). 也因此之故， “整数的除法”就成为一个需要人类探讨的问题。
(整数集在加法和乘法下构成环。)

\pause
\begin{definition}%定义1
  [整除]
  设 $a, b$ 均为整数， $b \neq 0$. 若存在整数 $q$ 使得
\[
a=b q
\]
则称 $b$ \emph{整除} $a$, 记为 $b \mid a$ (即 $b$ divides $a$ ); 
\pause
且称 $b$ 是 $a$ 的\emph{因子} (factor, divisor), $a$是 $b$ 的\emph{倍数}或\emph{倍} (multiple). 也可记为 $a \div b=q$, 称 $a$ 是\emph{被除数}， $b$ 是\emph{除数}， $q$ 是\emph{商}。
\pause
（反之， 如果不存在整数 $q$ 使得 $a=b q$, 则称 $b$ \emph{不整除} $a$, 记为 $b \nmid a$. )
\end{definition}

\pause
 例如： $2\mid 6,(-2)\mid  6,(-2)\mid (-6), 1\mid  7,(-1)\mid 7,7\mid  7,7 \mid 0$.
\end{frame}

\begin{frame}
注意， 任意非零整数 $b$ 整除 $0$, 因为 $0=b \cdot 0$ (但是， 约定永不用 $0$ 做除数). 整除性有如下简单性质(读者自证之):
\begin{proposition*}[整除的基本性质]
  (1) 若 $b \mid a$ 且 $a \mid b$, 则 $a= \pm b$. (整除的相伴性)\\
  (2) 若 $a\mid b, b\mid  c$ ，则 $a \mid c$. (整除的传递性)\\
  (3) 令$c \neq 0$. 那么$a \mid b$ 当且仅当 $a c \mid b c$. (整除的消去律)\\
(4) 若 $b \mid a_{1}$ 且 $b \mid a_{2}$, 则 $b \mid a_{1} \pm a_{2}$.
\end{proposition*}

\pause
设 $p \neq \pm 1$ 为非零整数， 而 $p$ 的正因子只有 $1$ 和 $|p|$, 则称 $p$ 为\emph{素数} (prime number). 
例如， $2,3,5,7$ 和 $-2,-3$ 都是素数。 
\pause
不是素数或 $\pm 1$ 的整数称为\emph{合数} (composite number). 例如， $4, 6, -6$ 都是合数。
\pause
换句话说， 素数是\emph{不可分解的}或\emph{不可约的}(即若素数 $p=b c$, 则必然 $b= \pm 1$ 或 $c= \pm 1$).
而合数\emph{可分解}或\emph{可约}， 即合数 $a$ 可写为 $a=b c$ (其中 $b, c \neq \pm 1$; 或者说 $b, c \neq \pm a$). 
\pause
注意， 若 $p$ 为素数， 则 $-p$ 也是素数。 故\emph{一般只考虑正素数}。
\pause
$1$ 不是素数。 小于 $100$ 的正素数为
\[
\begin{gathered}
  2,3,5,7,11,13,17,19,23,29,31,37,41 \\
43,47,53,59,61,67,71,73,79,83,89,97
\end{gathered}
\]
\pause
  确定一个给定的整数是素数或是合数是个基本的问题。这个被称为\emph{素性检验}。
  注意到
  \begin{lemma*}
    若一个正整数$n$是合数，则$n$有一个不超过$\sqrt{n}$的因子。
  \end{lemma*}
  %\begin{proof}
   % 设$n=ab$, 其中$1<a\leqslant b<n$. 显然$a\leqslant \sqrt{n}$.
  %\end{proof}
\end{frame}

\begin{frame}

  古希腊数学家Eratoshenes提出过一种找素数方法，现在被称为 \emph{Eratoshenes筛法}。
  \[
    \begin{tikzpicture}[column sep=1em, row sep=.5em]
      \pause
      \matrix (m) [matrix of math nodes, ampersand replacement=\&]
      {
        % 通过 ipython 把这个数表打印出来
        1 \& \symbf{2} \& \symbf{3} \& 4 \& \symbf{5} \& 6 \& \symbf{7} \& 8 \& 9 \& 10 \\
        \symbf{11} \& 12 \& \symbf{13} \& 14 \& 15 \& 16 \& \symbf{17} \& 18 \& \symbf{19} \& 20 \\
        21 \& 22 \& \symbf{23} \& 24 \& 25 \& 26 \& 27 \& 28 \& \symbf{29} \& 30 \\
        \symbf{31} \& 32 \& 33 \& 34 \& 35 \& 36 \& \symbf{37} \& 38 \& 39 \& 40 \\
        \symbf{41} \& 42 \& \symbf{43} \& 44 \& 45 \& 46 \& \symbf{47} \& 48 \& 49 \& 50 \\
        51 \& 52 \& \symbf{53} \& 54 \& 55 \& 56 \& 57 \& 58 \& \symbf{59} \& 60 \\
        \symbf{61} \& 62 \& 63 \& 64 \& 65 \& 66 \& \symbf{67} \& 68 \& 69 \& 70 \\
        \symbf{71} \& 72 \& \symbf{73} \& 74 \& 75 \& 76 \& 77 \& 78 \& \symbf{79} \& 80 \\
        81 \& 82 \& \symbf{83} \& 84 \& 85 \& 86 \& 87 \& 88 \& \symbf{89} \& 90 \\
        91 \& 92 \& 93 \& 94 \& 95 \& 96 \& \symbf{97} \& 98 \& 99 \& 100 \\
};
\pause
% 划去 1
\draw (m-1-1.south west) -- (m-1-1.north east);
\draw (m-1-1.south east) -- (m-1-1.north west);
\pause
% 划去 2 后面被 2 整除的数
\foreach \i in {4,6,8,10} {
  \draw (m-1-\i.west) -- (m-1-\i.east);
}
\foreach \j in {2,...,10} 
\foreach \i in {2,4,...,10} {
  \draw (m-\j-\i.west) -- (m-\j-\i.east);
}
\pause
% 划去 3 后面被 3 整除的还未被划去的数
\foreach \j/\i in {1/9, 2/5, 3/1, 3/7, 4/3, 4/9, 5/5, 6/1, 6/7, 7/3, 7/9, 8/5, 9/1, 9/7, 10/3, 10/9} {
\draw (m-\j-\i.south west) -- (m-\j-\i.north east);
}
\pause
% 划去 5 后面被 5 整除的还未被划去的数
\foreach \j/\i in {3/5, 4/5, 6/5, 7/5, 9/5, 10/5} {
\draw (m-\j-\i.south east) -- (m-\j-\i.north west);
}
\pause
% 划去 7 后面被 7 整除的还未被划去的数
\foreach \j/\i in {5/9, 8/7, 10/1} {
\draw (m-\j-\i.north) -- (m-\j-\i.south);
}
\pause
    \end{tikzpicture}
  \]
\uncover<+->{%
更多的素数见附录 7. 
将证明， 素数有无限多个。 
}%
\uncover<+->{%
以 $\pi(x)$ 记不超过正数 $x$的正素数个数， 则 $\pi(x)$ 与 $x / \ln x$ 近似 (素数定理\footnote{15岁的高斯如此猜测，由Hadamard和Vallée Poussin独立证明。}), 即$\lim_{x\rightarrow \infty} \frac{\pi(x)}{x/\ln x}=1$. % (这里 $\mathrm{e}=2.71828 \cdots$ 是自然对数 $\ln x$ 的底).
这是关于素数分布的最著名的定理。
}
\end{frame}

\begin{frame}
  \begin{lemma}%引理1
    [因子分解] 任一非$0$非$\pm 1$的整数 $n$ 可写为有限个素数之积。
\end{lemma}
\pause
\begin{proof}
只需对自然数 $n$ 证明。 用数学归纳法。
\pause
首先， 对 $n=2$, 引理显然成立（此称为\emph{归纳起点}）. 
\pause
假设对任意固定的自然数 $n>2$, 引理对小于 $n$ 的自然数均成立(此称为\emph{归纳法假设}); 
现需要证明引理对 $n$ 成立（此为\emph{归纳法关键步骤}). 
\pause
(i) 若 $n$ 是素数， 自然是一个素数之积， 引理对 $n$ 成立。
\pause
(ii) 若 $n$ 不是素数， 则可写为 $n=m q$, 其中 $m, q$ 为小于 $n$ 的自然数， 由归纳法假设可知， $m, q$均为有限个素数之积， 可写为 $m=p_{1} \cdots p_{s}, q=p_{s+1} \cdots p_{t}$, 二者相乘， 可知 $n=m q=p_{1} \cdots p_{s} p_{s+1} \cdots p_{t}$ 为有限个素数之积， 故引理对 $n$ 成立。 证毕。
 \end{proof}

 \pause
 \begin{explain*}%说明
   数学归纳法 (的有效性)是基于“自然数集的每个非空子集都含有最小数”(这称为\emph{自然数的良序性}). 事实上， 假若经过数学归纳法证明后定理仍对某些自然数不成立， 则不满足定理的自然数子集合必含最小数(据自然数的良序性), 记为 $n_{0}$. 因为 $n_{0}$ 最小，所以对小于 $n_{0}$ 的自然数定理都成立。 而我们在数学归纳法的关键步骤中已经证明了：“假设定理对小于 $n_{0}$ 的自然数均成立， 则定理对 $n_{0}$ 成立”, 故矛盾。 此矛盾表明了数学归纳法的有效性。
 \end{explain*}

\pause
 引理 1 中 “ $n$ 写为素数之积”被称为 $n$ 的（素）\emph{因子分解}， 或\emph{析因} (factorization). 以后， 我们会证明这种分解是唯一的， 称为 “\emph{唯一析因}”. 常约定 “ $1$ 是 $0$ 个素数之积”.
\end{frame}

\begin{frame}
  \begin{theorem}%定理1
    [带余除法， Euclid(欧几里得) 除法， Euclidean division] 若 $a, b$均为整数， $b \neq 0$, 则存在整数 $q$ 和 $r$ 使得
\[
a=b q+r, \quad 0 \leqslant r<|b|
\]
且 $q$ 和 $r$ 是唯一的。
\end{theorem}

\pause
\begin{explain*}%说明
  定理 1 中的 $r$ 称为\emph{余数} (remainder), $q$ 称为\emph{不完全商} (quotient). 当
$b>0$ 时， 带余除式可改写为
\[
\frac{a}{b}=q+\frac{r}{b}, \quad 0 \leqslant \frac{r}{b}<1
\]
可见 $q=\left\lfloor\frac{a}{b}\right\rfloor$ 是 $\frac{a}{b}$ 的整数部分， 即不超过 $\frac{a}{b}$ 的最大整数。
\pause
$[x]$和$\lfloor x\rfloor$通常用于表示不超过实数$x$的最大整数，称为$x$的\emph{整数部分} (integral part)；
$\left\{ x \right\}=x-[x]\in [0,1)$称为实数$x$的\emph{小数部分} (fractional part)。
$\lceil x\rceil$通常用于表示不小于实数$x$的最小整数。
\end{explain*}

\pause
\begin{proof*}[定理1的证明]
考虑集合$S=a+b\ZZ=\{a+bl\mid l\in\ZZ\}$. 
  $S$中包含非负整数，可取$S$中最小的非负整数$r$. 若$r\geqslant |b|$, $r-|b|\in S$是更小的$S$中的非负整数。
  所以只有$0\leqslant r<|b|$. 这就证明了带余除法的存在性。唯一性略。
%
% 先设 $b>0$, 取 $q=\left\lfloor\frac{a}{b}\right\rfloor$, 令 $r=a-b q$, 则得 $a=b q+r$. 也可考虑整数序列
% \[
% \cdots, \quad-3 b, \quad-2 b, \quad-b, \quad 0, \quad b, \quad 2 b, \quad 3 b, \cdots
% \]
% (这些整数将实数轴分割为无限多个长为 $b$ 的小段， 则 $a$ 必落在某小段之中，设落在 $q b$ 与 $(q+1) b$ 之间). 则必存在整数 $q$ 使
% \[
% q b \leqslant a<(q+1) b
% \]
% 令 $r=a-q b$ (即 $a$ 到小段左端点的距离), 则得到带余除式 $a=b q+r$ 且 $0 \leqslant r<b$.
%
% 当 $b<0$ 时， 则 $b^{\prime}=-b>0$, 故有 $a=(-b) q^{\prime}+r$ 且 $0 \leqslant r<(-b)$. 令 $q=-q^{\prime}$, 则化为 $a=(-b)(-q)+r=b q+r$ 且 $0 \leqslant r<|b|$.
%
% 现证 $q$ 和 $r$ 是唯一的。 假若 $a=b q+r=b q_{1}+r_{1}$. 相减得到 $b\left(q-q_{1}\right)=r_{1}-r$. 若 $q-q_{1} \neq 0$, 则 $\left|r_{1}-r\right|=\left|b\left(q-q_{1}\right)\right| \geqslant|b|$, 矛盾 (因 $0 \leqslant r, r_{1}<|b|$ ). 所以 $q=q_{1}$, 从而 $r=r_{1}$.
 \end{proof*}

 \pause
 定理 1 中的余数 $r$ 满足 $0 \leqslant r<|b|$, 称为\emph{最小非负(剩) 余数}。 我们也可以要求余数 $r^{\prime}$ 满足 $-|b| / 2<r^{\prime} \leqslant|b| / 2$, 称为\emph{绝对 (值)最小 (剩) 余数}。
\end{frame}

\begin{frame}
  \begin{comment*}%评述
    L. Kronecker (克罗内克，1823-1891)有名言 : “上帝创造了自然数，其余的一切皆是人为 (God made natural numbers; all else is the work of man)."然而， 整数集 $\mathbb{Z}$ 才是数论的首个良好用武之地。 $\mathbb{Z}$ 对加、减、乘法封闭 (因而称为\emph{环}). 整数的除法常遗留余数(带余除法), 这是整数集的最重要性质 (因而称为 \emph{Euclid 环})，它可推导出整数许多其他性质。

整数的这些性质， 在两千多年前古希腊即已发现， 例如在 Euclid 的 Elements(《几何原本》) 中。 但至今鲜亮夺目、意义非凡。 论数者单道这“整数之奇妙” :\\
\begin{poem}
开辟鸿蒙先有一， 一生二三整数集。\\
加减乘法皆封闭， 除法有遗生传奇。
\end{poem}
\end{comment*}

\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 考虑整数。何为整除、因子、倍？
    \item 何为素数、合数？
    \item 叙述整数的因子分解性。
    \item 何为带余除法？
  \end{enumerate}
\end{frame}
